package com.lwt.codetop.linkedLists;

// 19. 删除链表的倒数第 N 个结点

/**
 * 思路：首先要找到要删除位置的前驱（倒数第n个即，顺数的len - n个），然后删除
 */
public class RemoveNthNodeFromEndOfList {
    public static void main(String[] args) {
        // 构建测试用例
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        int n = 2;
        // 删除倒数第n个节点
        ListNode res = removeNthFromEnd(head, n);
        while (res != null){
            System.out.print(res.val + " ");
            res = res.next;
        }
    }

    private static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 统计链表长度
        ListNode p = dummy;
        int len = 0;
        while(p != null){
            p = p.next;
            len += 1;
        }
        // 找到倒数第n个节点的前驱
        p = dummy;
        for (int i = 0; i < len - n - 1; i++) {
            p = p.next;
        }
        // 删除
        p.next = p.next.next;
        return dummy.next;
    }
}
